def get_next(patt):
    next = [0]
    prefix_len = 0
    i = 1
    while i<len(patt):
        if patt[prefix_len] == patt[i]:
            prefix_len += 1
            next.append(prefix_len)
            i+=1
        else:
            if prefix_len==0:
                next.append(0)
                i+=1
            else: 
                prefix_len = next[prefix_len-1]
    return next

def KMP_search(string,patt):
    next = get_next(patt)
    i = 0
    j = 0
    while i< len(string):
        if string[i] == patt[j]:
            i+=1
            j+=1
        elif j>0:
            j = next[j-1]
        else:
            i+=1
        if j == len(patt):
            return i-j
        
if __name__ == "__main__" :
    print(KMP_search("ss1sss1qqe", "1qq"))